# a clean solution, O(n)

class Solution(object):
    def candy(self, ratings):
        length = len(ratings)
        if length==0: return 0
        elif length==1: return 1

        nums = [1] * length
        for i, this in enumerate(ratings):
            last = ratings[i-1] if 0<=i-1 else None
            next = ratings[i+1] if i+1<length else None
            print(nums)
            if last==None:
                if next>this:
                    for j in range(i+1, length):
                        if ratings[j]>ratings[j-1]:
                            nums[j]=max(nums[j], nums[j-1]+1)
                        else:
                            break
            elif next==None:
                if last>this:
                    for j in range(i)[::-1]:
                        if ratings[j]>ratings[j+1]:
                            nums[j]=max(nums[j], nums[j+1]+1)
                        else:
                            break
            elif last>=this and next>=this and last+next>2*this:
                for j in range(i+1, length):
                    if ratings[j]>ratings[j-1]:
                        nums[j]=max(nums[j], nums[j-1]+1)
                    else:
                        break
                for j in range(i)[::-1]:
                    if ratings[j]>ratings[j+1]:
                        nums[j]=max(nums[j], nums[j+1]+1)
                    else:
                        break
        return sum(nums)

print(Solution().candy([5,1,1,1,10,2,1,1,1,3]))